Recent advances in computer performance have enabled graphic systems to provide more realistic graphical images using personal computers, home video game computers, handheld devices, and the like. In such graphic systems, a number of procedures are executed to “render” or draw graphic primitives to the screen of the system. A “graphic primitive” is a basic component of a graphic picture, such as a vertex, polygon, or the like. Rendered images are formed with combinations of these graphic primitives. Many procedures may be utilized to perform 3-D graphics rendering.
Specialized graphics processing units (e.g., GPUs, etc.) have been developed to optimize the computations required in executing the graphics rendering procedures. The GPUs are configured for high-speed operation and typically incorporate one or more rendering pipelines. Each pipeline includes a number of hardware-based functional units that are optimized for high-speed execution of graphics instructions/data, where the instructions/data are fed into the front end of the pipeline and the computed results emerge at the back end of the pipeline. The hardware-based functional units, cache memories, firmware, and the like, of the GPU are optimized to operate on the low-level graphics primitives (e.g., comprising “points”, “lines”, “triangles”, etc.) and produce real-time rendered 3-D images.
The real-time rendered 3-D images are generated using raster display technology. Raster display technology is widely used in computer graphics systems, and generally refers to the mechanism by which the grid of multiple pixels comprising an image are influenced by the graphics primitives. For each primitive, a typical rasterization system generally steps from pixel to pixel and determines whether or not to “render,” or write a given pixel into a frame buffer or pixel map, as per the contribution of the primitive. This, in turn, determines how to write the data to the display buffer representing each pixel.
Various traversal algorithms have been developed for moving from pixel to pixel in a way such that all pixels within a primitive are covered. The traversal algorithms need to take into account a clipping window in which the primitives comprising an image are to be rendered.
Generally, a clipping window comprises a data structure (e.g., rectangle data structure, window clip plane, etc.) that is used to represent the visible areas of an image. GPUs include special hardware and/or software for holding the clipping information in order to properly clip graphics primitives. The viewing, perspective, and clipping stages require a large number of arithmetic operations for the vertices and edges of each polygon received.
A problem exists, however, in rasterizing primitives that only partially reside within a clipping window. Typical prior art solutions involve rasterizing primitives and generating the resulting covered pixels in a unidirectional manner. Such traditional unidirectional solutions involve generating the pixels row-by-row in a constant direction. The traditional solutions begin at one edge of the clipping window and traverse across the clipping window until the primitive is encountered, and then step across the primitive until a line of rasterization complete. This requires that the sequence shift across the image to find the edge of the primitive. When the edge of the primitive is outside the clipping window, the traditional solutions are required to step from the starting edge and traverse across the primitive until they step into the visible region of the primitive (e.g., the portion within the clipping window).
Thus a large amount of work and a corresponding large number of clock cycles are consumed rasterizing pixels that ultimately will not be rendered within the image. This results in a very large negative performance impact on the overall 3-D rendering process. The negative performance impact is even more pronounced for those primitives having a majority of their area outside the clipping window (e.g., long thin triangles that are often encountered in shadowing applications).
Accordingly, a need exists for a rasterization process that can ensure needed graphics rendering hardware, and clock cycles consumed by that rendering hardware, are productively utilized generating pixels that are relevant to the image being created.